package com.eloancn.leecode.classic;
/**
 * 链表环路检测
 * @author lihepeng
 *给定一个有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。

 */
public class DetectCycle {
	// 快慢指针法
	public ListNode detectCycle(ListNode head) {
		ListNode s = head;
		ListNode f = head;
		while(true) {
			s = s.next;
			f = f.next.next;
			if (s==f) {
				return s; 
			}
			if(s.next == null) {
				return null;
			}
			
		}
		
	}
	class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      			}
		 }
}
